package com.practice.shua1;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * 【题目】：（TODO：单调栈）
 * 在数组中想找到一个数， 左边和右边比这个数小、 且离这个数最近的位置。
 * 如果对每一个数都想求这样的信息， 能不能整体代价达到O(N)？
 * 需要使用到单调栈结构
 * 单调栈结构的原理和实现
 */
public class Code_05_MonotonousStack {

    /*
     * 求里你最近比你小的数， 栈底--->栈顶 ： 小 ---> 大，
     * 一个东西从栈中出来时生成记录，让你出来的数是右边离你最近比你小的（没有就是null），栈中你压着的数是左边离你最近比你小的（没有就是null）
     * 最后单独处理栈中剩余的记录（依次弹出，出来时按照上面的规则得到左边距离它最近比它小的数、右边距离它最近比它小的数都是null）
     *
     * 求里你最近比你大的数， 栈底--->栈顶 ： 大 ---> 小，
     * 一个东西从栈中出来时生成记录，让你出来的数是右边离你最近比你大的（没有就是null），栈中你压着的数是左边离你最近比你大的（没有就是null）
     * 最后单独处理栈中剩余的记录（依次弹出，出来时按照上面的规则得到左边距离它最近比它大的数、右边距离它最近比它大的数都是null）
     *
     * 栈中放的值下标，是index
     *
     * 如果有重复值，栈中存放的每个元素就是index的列表，LinkedList<Integer>, 例如 [index1, index2, index3...indexN]
     * 放入一个数时，如果发现其与栈顶代表的值相等，直接将其下标放到栈顶列表的末尾
     * 每次弹出，弹出的是一个列表，左边比他们小的离他们最近的是其小面压着的列表中最末尾的元素
     *
     */


    // 我自己写的，允许重复元素的单调栈解法
    public static int[][] myAnswerCanRepeat(int[] arr){
        // res[i][0]代表arr[i]左边离它最近比它小的数的下标, res[i][1]代表arr[i]右边离它最近比它小的数的下标
        int[][] res = new int[arr.length][2];
        Stack<LinkedList<Integer>> stack = new Stack<>();
        int i = 0;
        while (i < arr.length){
            if (!stack.isEmpty()){
                LinkedList<Integer> topIndexList = stack.peek();
                Integer index = topIndexList.get(0);
                if (arr[index] < arr[i]){
                    // 进
                    LinkedList<Integer> curIndexList = new LinkedList<>();
                    curIndexList.add(i);
                    stack.push(curIndexList);
                    i++;
                }else if (arr[index]==arr[i]){
                    // 进
                    topIndexList.add(i);
                    i++;
                }else {
                    // 弹
                    LinkedList<Integer> popIndexList = stack.pop();
                    LinkedList<Integer> nextIndexList = null;
                    if (!stack.isEmpty()){
                        nextIndexList= stack.peek();
                    }
                    for (int j = 0; j < popIndexList.size(); j++) {
                        Integer tempIndex = popIndexList.get(j);
                        if (nextIndexList == null){
                            res[tempIndex][0] = -1;
                        }else {
                            res[tempIndex][0] = nextIndexList.get(nextIndexList.size()-1);
                        }
                        res[tempIndex][1] = i;
                    }
                    // i不变，继续在循环中跟栈顶比较
                }
            }else {
                LinkedList<Integer> curIndexList = new LinkedList<>();
                curIndexList.add(i);
                stack.push(curIndexList);
                i++;
            }
        }
        // 将栈中剩余的列表弹出
        while (!stack.isEmpty()){
            LinkedList<Integer> popIndexList = stack.pop();
            LinkedList<Integer> nextIndexList = null;
            if (!stack.isEmpty()){
                nextIndexList= stack.peek();
            }
            for (int j = 0; j < popIndexList.size(); j++) {
                Integer tempIndex = popIndexList.get(j);
                if (nextIndexList == null){
                    res[tempIndex][0] = -1;
                }else {
                    res[tempIndex][0] = nextIndexList.get(nextIndexList.size()-1);
                }
                res[tempIndex][1] = -1;
            }
        }
        return res;
    }





    // 没有重复值的情况
    public static int[][] getNearLessNoRepeat(int[] arr) {
        int[][] res = new int[arr.length][2];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < arr.length; i++) {
            while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
                int popIndex = stack.pop();
                int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
                res[popIndex][0] = leftLessIndex;
                res[popIndex][1] = i;
            }
            stack.push(i);
        }
        while (!stack.isEmpty()) {
            int popIndex = stack.pop();
            int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
            res[popIndex][0] = leftLessIndex;
            res[popIndex][1] = -1;
        }
        return res;
    }

    // arr [3, 2, 1, 4, 5]
    //      0  1  2  3  4

    //  [
    //    0 :  [-1,  1  ]
    //    1 :  [-1,  2  ]

    //  ]
    //
    // 有重复值的情况
    public static int[][] getNearLess(int[] arr) {
        int[][] res = new int[arr.length][2];


        // List<Integer> -> 放的是位置，同样值的东西，位置压在一起
        // 代表值    底  ->  顶   小  -> 大
        Stack<List<Integer>> stack = new Stack<>();
        for (int i = 0; i < arr.length; i++) { // i -> arr[i] 进栈
            // 底 -> 顶， 小 -> 大
            while (!stack.isEmpty() && arr[stack.peek().get(0)] > arr[i]) {
                List<Integer> popIs = stack.pop();
                // 取位于下面位置的列表中，最晚加入的那个
                int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);
                for (Integer popi : popIs) {
                    res[popi][0] = leftLessIndex;
                    res[popi][1] = i;
                }
            }
            // 相等的、比你小的
            if (!stack.isEmpty() && arr[stack.peek().get(0)] == arr[i]) {
                stack.peek().add(Integer.valueOf(i));
            } else {
                ArrayList<Integer> list = new ArrayList<>();
                list.add(i);
                stack.push(list);
            }
        }
        while (!stack.isEmpty()) {
            List<Integer> popIs = stack.pop();
            // 取位于下面位置的列表中，最晚加入的那个
            int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);
            for (Integer popi : popIs) {
                res[popi][0] = leftLessIndex;
                res[popi][1] = -1;
            }
        }
        return res;
    }
















    // for test
    public static int[] getRandomArrayNoRepeat(int size) {
        int[] arr = new int[(int) (Math.random() * size) + 1];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = i;
        }
        for (int i = 0; i < arr.length; i++) {
            int swapIndex = (int) (Math.random() * arr.length);
            int tmp = arr[swapIndex];
            arr[swapIndex] = arr[i];
            arr[i] = tmp;
        }
        return arr;
    }

    // for test
    public static int[] getRandomArray(int size, int max) {
        int[] arr = new int[(int) (Math.random() * size) + 1];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * max) - (int) (Math.random() * max);
        }
        return arr;
    }

    // for test
    public static int[][] rightWay(int[] arr) {
        int[][] res = new int[arr.length][2];
        for (int i = 0; i < arr.length; i++) {
            int leftLessIndex = -1;
            int rightLessIndex = -1;
            int cur = i - 1;
            while (cur >= 0) {
                if (arr[cur] < arr[i]) {
                    leftLessIndex = cur;
                    break;
                }
                cur--;
            }
            cur = i + 1;
            while (cur < arr.length) {
                if (arr[cur] < arr[i]) {
                    rightLessIndex = cur;
                    break;
                }
                cur++;
            }
            res[i][0] = leftLessIndex;
            res[i][1] = rightLessIndex;
        }
        return res;
    }

    // for test
    public static boolean isEqual(int[][] res1, int[][] res2) {
        if (res1.length != res2.length) {
            return false;
        }
        for (int i = 0; i < res1.length; i++) {
            if (res1[i][0] != res2[i][0] || res1[i][1] != res2[i][1]) {
                return false;
            }
        }

        return true;
    }

    // for test
    public static void printArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int size = 10;
        int max = 20;
        int testTimes = 2000000;
        for (int i = 0; i < testTimes; i++) {
            int[] arr1 = getRandomArrayNoRepeat(size);
            int[] arr2 = getRandomArray(size, max);
            int[] arr3 = getRandomArray(size, max);
            if (!isEqual(getNearLessNoRepeat(arr1), rightWay(arr1))) {
                System.out.println("Oops!");
                printArray(arr1);
                break;
            }
            if (!isEqual(getNearLess(arr2), rightWay(arr2))) {
                System.out.println("Oops!");
                printArray(arr2);
                break;
            }
            if (!isEqual(myAnswerCanRepeat(arr3), rightWay(arr3))) {
                System.out.println("Oops!");
                printArray(arr3);
                break;
            }
        }
        System.out.println("niubila");
    }
}
